FIG. 1 depicts a schematic diagram of a portion of a typical wireless telecommunications system in the prior art, which system provides wireless telecommunications service to a number of wireless terminals (e.g., wireless terminals 101-1 through 101-3) that are situated within a geographic region. The heart of a typical wireless telecommunications system is a wireless switching center ("WSC"), which may also be known as a mobile switching center ("MSC") or mobile telephone switching office ("MTSO"). Typically, a wireless switching center (e.g, WSC 120) is connected to a plurality of base stations (e.g., base stations 103-1 through 103-5) that are dispersed throughout the geographic area serviced by the system and to the local and long-distance telephone and data networks (e.g., local-office 130, local-office 138 and toll-office 140). A wireless switching center is responsible for, among other things, establishing and maintaining a call between a first wireless terminal and a second wireless terminal or, alternatively, between the first wireless terminal and a wireline terminal (e.g., wireline terminal 150), which is connected to the system via the local and/or long-distance networks.
The geographic area serviced by a wireless telecommunications system is partitioned into a number of spatially distinct areas called "cells." As depicted in FIG. 1, each cell is schematically represented by one hexagon and the cells are tessellated in a honeycomb pattern. In practice, however, each cell has an irregular shape that depends on the topography of the terrain surrounding the cell. Typically, each cell contains a base station, which comprises the radios and antennas that the base station uses to communicate with the wireless terminals in that cell and also comprises the transmission equipment that the base station uses to communicate with the wireless switching center.
For example, when a user of wireless terminal 101-1 desires to transmit information to a user of wireless terminal 101-2, wireless terminal 101-1 transmits a data message bearing the user's information to base station 103-1. The data message is then relayed by base station 103-1 to wireless switching center 120 via wireline 102-1. Because wireless terminal 101-2 is in the cell serviced by base station 103-1, wireless switching center 120 returns the data message back to base station 103-1, which relays it to wireless terminal 101-2.
Not only does a base station transmit data messages to the wireless terminals within its cell, but it also transmits control messages as well. In general, the control messages are the means by which a base station coordinates its operation with a wireless terminal. Although a wireless terminal typically receives dozens of control messages every second, it is unlikely that a user of the wireless terminal is aware of that fact, or of the fact that the wireless terminal also acts on and replies to some of those control messages.
FIG. 2 depicts a block diagram of the salient components of base station 103-1 for the generation, accumulation, and transmission of control messages. Base station 103-1 comprises base station controller 201 and forward paging subsystem 202, which accumulates the control messages and transmits them over forward paging channel 203.
Some control messages are generated by wireless switching center 120 and are received by forward paging subsystem 202 via wireline 102-1. Other control messages are generated by base station controller 201 and are received by forward paging subsystem 202 via connection 204. As the control messages are received by forward paging subsystem 202, they are queued pending transmission.
When there is only one control message queued, it is transmitted as soon as possible. In contrast, when there is more than one control message queued, forward paging subsystem 202 must transmit one of the control messages before the others. At first, it may appear that the messages must be transmitted in the same order in which they arrive, but that is not the case. When there are H control messages in a queue, there are H! different orders in which they can be transmitted. Furthermore, each of the H! different orders can have a significantly different effect. Therefore, the process for selecting an order by which forward paging subsystem 202 transmits control messages should carefully consider the ramifications of the selected order.
The same is true for any situation in which there are more people, objects, tasks, messages, etc. in a queue for processing, shipping, completion, transmission, etc. given finite resources for doing so. For example, if 2500 people on a sinking ship are queued to board lifeboats with a total capacity of only 800, then the process for selecting the order by which the people enter the lifeboats has dire ramifications.
For the purposes of this specification, the term "queue discipline" refers to the process for determining how people, objects, tasks, messages, etc. in a queue are ordered for processing, shipping, completion, transmission, etc. given finite resources for doing so. Although some queue disciplines are intentionally established and enforced in society (e.g., at a supermarket check-out, in a hospital emergency room, on a sinking ship, etc.), others follow naturally from cultural norms (e.g., woman and children first, age before beauty, etc.) or logistics (e.g., the last people into a crowded elevator should be the first ones out, etc.). For example:
first-in, first-out ("FIFO")-A first-in, first-out queue discipline processes people, objects, tasks, messages, etc. strictly in the order in which they arrive. A supermarket check-out line is a typical example of a first-in, first-out queue discipline. PA1 triage-A triage queue discipline processes people, objects, tasks, messages, etc. based on the need for or likely benefit from processing. Triage is typically used on a battlefield, at disaster sites, and in hospital emergency rooms when limited medical resources must be allocated. Strictly, there is no single triage queue discipline. Instead, there are a number of triage queue disciplines that are distinguishable based on the specific criteria used to define the need for or likely benefit from processing. Furthermore, the differences between one triage queue discipline and another can be subtle. PA1 last-in, first-out ("LIFO")-A last-in, first-out queue discipline processes people, objects, tasks, messages, etc. strictly in the reverse order in which they arrive. A typical last-in, first-out queue discipline can be observed at crowded elevators where the last people into the elevator are the first ones out. PA1 random-A random queue discipline processes people, objects, tasks, messages, etc. randomly, regardless of the order in which they arrive or any other factor. A typical random queue discipline is a lottery system, because the likelihood of winning is based on a random drawing and not on the order in which the lottery tickets are sold or any other demonstrable factor.
The selection of a queue discipline for forward paging subsystem 202 has a significant effect on the economic viability of the entire telecommunications system. Furthermore, there are six factors that must be considered in choosing a queue discipline for forward paging subsystem 202.
First, the bandwidth of forward paging channel 203 is finite, and, therefore, the mean rate at which control messages can be transmitted, .mu., over forward paging channel 203 is also finite. If the mean rate at which control messages arrive, .lambda., at forward paging subsystem 202 is greater than the mean rate at which they can be transmitted (i.e., if .lambda.&gt;.mu.), then not all of the control messages can be transmitted. This militates against a first-in, first-out queue discipline and suggests that a triage queue discipline be chosen where control messages of higher priority are transmitted before messages of lower priority.
Second, each control message is perishable (i.e., the usefulness of the information in a control message is dependent on the amount of time that it takes to reach its destination). Furthermore, the operation of the telecommunication system can collapse if some of the highest priority control messages are not transmitted in a timely manner. This suggests that when forward paging subsystem 202 determines the order in which to transmit a plurality of control messages, it should consider the perishability of the control messages, in addition to their relative priority. For example, it is conceivable that a highly-perishable, low-priority control message should be transmitted before a less-perishable, high-priority one.
Third, control messages arrive at forward paging subsystem 202 successively (i.e., one after another in contrast to in bulk), sporadically, and sometimes at a greater rate than they can be transmitted. So although situations may occur in which an arriving control message can be transmitted immediately and without delay, there are also situations in which control messages must wait to be transmitted. The mean wait, T, of a control message pending transmission is: ##EQU1##
where .mu. is the mean rate at which control messages can be transmitted over forward paging channel 203 and .lambda. is the mean rate at which control messages arrive at forward paging subsystem 202. Furthermore, because the arrival of control messages is sporadic, the amount of time that a given control message must wait to be transmitted is unpredictable. This suggests that when forward paging subsystem 202 determines the order in which to transmit a plurality of control messages, it should consider the uncertainty in delay that a control message can experience before it is transmitted in addition to the perishability of the message.
Fourth, there are several classes of control messages. If two or more control messages in the same class are transmitted successively on forward paging channel 203, then an economy of scale can be achieved that effectively increases the mean rate, .mu., at which control messages can be transmitted. The economy of scale results from the fact that two or more control messages in the same class that are transmitted successively can share a common header, as is discussed below. Furthermore, an increase in the mean rate, .mu., at which control messages can be transmitted causes a corresponding decrease in the mean wait, T, of a control message. Therefore, this suggests that forward paging subsystem 202 should accumulate control messages for a while so that as many of the same class can be transmitted successively.
Fifth, many of the factors affecting T(e.g., .mu., .lambda., the mix of control messages, etc.) are likely to change over time and vary with location. For example, the factors affecting T are likely to change with the time of day, the day of the week, the seasons, etc. Furthermore, the factors affecting T are likely to be different in Wyoming than in New York. Therefore, forward paging channel 203 must implement a queue discipline that is sophisticated enough to consider and balance the wide range of factors affecting T.
Sixth, statistical data on the factors affecting T may not be known before forward paging subsystem 202 is placed into service, and, therefore, the queue discipline in forward paging channel 203 should be reconfigurable in the field after empirical data for that locale has been gathered.
In summary, the need exists for a forward paging subsystem that: (1) is sophisticated enough to consider and balance the wide range of factors affecting T, (2) attempts to transmit the more perishable control messages before the less perishable, (3) attempts to transmit the higher priority control messages before the lower priority ones, and (4) is quickly and easily reconfigured in the field.